/////////////////////////////////////////////////////////////////////////////
/// @file AvlTree_TestSuite.cpp
/// @ingroup
///
/// File containing the implementation for testing AvlTree class implementation
/// Unit under test: AvlTree.hpp
///
/// @see AvlTree_TestSuite.hpp
///
/// @if REVISION_HISTORY_INCLUDED
/// @par Edit History
/// @li [0]   zhalat 19-Aug-2014 Initial revision of file.
/// @endif
///
/// @par &copy;  2014 HalSoft
/////////////////////////////////////////////////////////////////////////////

// SYSTEM INCLUDES

// C++ PROJECT INCLUDES
#include "AvlTree_TestSuite.hpp"

using namespace tree;

CppUnit::Test* AvlTree_TestSuite::suite(){
    CppUnit::TestSuite* suiteOfTests = new CppUnit::TestSuite("AvlTree_TestSuite");
    //tree's element is in-build type
    suiteOfTests->addTest(new CppUnit::TestCaller<AvlTree_TestSuite>("test_RR_rot_emb", &AvlTree_TestSuite::test_RR_rot_emb));
    suiteOfTests->addTest(new CppUnit::TestCaller<AvlTree_TestSuite>("test_LL_rot_emb", &AvlTree_TestSuite::test_LL_rot_emb));
    suiteOfTests->addTest(new CppUnit::TestCaller<AvlTree_TestSuite>("test_RL_rot_emb", &AvlTree_TestSuite::test_RL_rot_emb));
    suiteOfTests->addTest(new CppUnit::TestCaller<AvlTree_TestSuite>("test_LR_rot_emb", &AvlTree_TestSuite::test_LR_rot_emb));
    suiteOfTests->addTest(new CppUnit::TestCaller<AvlTree_TestSuite>("test_rot_emb", &AvlTree_TestSuite::test_rot_emb));
    suiteOfTests->addTest(new CppUnit::TestCaller<AvlTree_TestSuite>("test_ins_emb", &AvlTree_TestSuite::test_ins_emb));


    return suiteOfTests;
}

//***************************************************************************
// Testing method: RR_rot()
//***************************************************************************
void AvlTree_TestSuite::test_RR_rot_emb(void){

    BTNode<int>* temp1;
    //create a simple test tree:
    /*
     *   1    - 2
     *   2    - 3
     *   3    - -
     */
    temp1 = emb_avl->ins_right( NULL, 1 );    temp1->bt = -2;
    temp1 = emb_avl->ins_right( temp1, 2 ); temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 3 ); temp1->bt =  0;

    //negative - bt out of scope
    temp1 = emb_avl->biroot();
    temp1->pRight->bt=1;
    CPPUNIT_ASSERT( false == emb_avl->RR_rot(emb_avl->biroot()) );

    //positive - bt OK
    temp1->pRight->bt=-1;
    CPPUNIT_ASSERT( true == emb_avl->RR_rot(emb_avl->biroot()) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT( 2 == temp1->data && 1 == temp1->pLeft->data && 3 == temp1->pRight->data );
    //checking: pointers
    CPPUNIT_ASSERT( NULL == temp1->pup && temp1 == temp1->pRight->pup && temp1 == temp1->pLeft->pup );
    //checking: balance
    CPPUNIT_ASSERT( 0 == temp1->bt && 0 == temp1->pLeft->bt && 0 == temp1->pRight->bt );

    emb_avl->rem_left(NULL);
    //create test tree:
    /*
     *    0     4   8
     *    4     -   -
     *    8  9   10
     *    9  20  -
     *   10     -   21
     *   20  -   -
     *   21  -   -
     */
    temp1 = emb_avl->ins_right( NULL, 0 );   temp1->bt = -2;
            emb_avl->ins_left( temp1, 4 );     temp1->pLeft->bt = 0;
    temp1 = emb_avl->ins_right( temp1, 8 );  temp1->bt = 0;
    temp1 = emb_avl->ins_left( temp1, 9 );     temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 20 );  temp1->bt = 0;
    temp1 = emb_avl->biroot()->pRight;
    temp1 = emb_avl->ins_right( temp1, 10 ); temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 21 ); temp1->bt = 0;
    CPPUNIT_ASSERT( true == emb_avl->RR_rot( emb_avl->biroot()) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT( 8 == temp1->data && 0 == temp1->pLeft->data && 10 == temp1->pRight->data &&
                    4 == temp1->pLeft->pLeft->data && 9 == temp1->pLeft->pRight->data && 20 == temp1->pLeft->pRight->pLeft->data &&
                    21 ==  temp1->pRight->pRight->data &&
                    NULL == temp1->pLeft->pLeft->pLeft && NULL == temp1->pLeft->pLeft->pRight &&
                    NULL == temp1->pLeft->pRight->pRight && NULL == temp1->pRight->pLeft &&
                    NULL == temp1->pRight->pRight->pRight && NULL == temp1->pRight->pRight->pLeft);
    //checking: pointers
    CPPUNIT_ASSERT( NULL == temp1->pup && 8 == temp1->pRight->pup->data && 8 == temp1->pLeft->pup->data &&
                    0 == temp1->pLeft->pLeft->pup->data && 0 == temp1->pLeft->pRight->pup->data &&
                    9 == temp1->pLeft->pRight->pLeft->pup->data && 10 == temp1->pRight->pRight->pup->data );
    //checking: balance
    CPPUNIT_ASSERT(  1 == temp1->bt &&
                    -1 == temp1->pLeft->bt &&
                    -1 == temp1->pRight->bt &&
                     0 == temp1->pLeft->pLeft->bt &&
                     1 == temp1->pLeft->pRight->bt &&
                     0 == temp1->pLeft->pRight->pLeft->bt &&
                     0 == temp1->pRight->pRight->bt
                   );
}

//***************************************************************************
// Testing method: LL_rot()
//***************************************************************************
void AvlTree_TestSuite::test_LL_rot_emb(void){

    BTNode<int>* temp1;
    //create a simple test tree:
    /*
     *   1    2 -
     *   2    3 -
     *   3    - -
     */
    temp1 = emb_avl->ins_left( NULL, 1 );  temp1->bt =  2;
    temp1 = emb_avl->ins_left( temp1, 2 ); temp1->bt =  1;
    temp1 = emb_avl->ins_left( temp1, 3 ); temp1->bt =  0;

    //negative - bt out of scope
    temp1 = emb_avl->biroot();
    temp1->pLeft->bt = -1;
    CPPUNIT_ASSERT( false == emb_avl->LL_rot( emb_avl->biroot()) );

    //positive - bt OK
    temp1->pLeft->bt = 1;
    CPPUNIT_ASSERT( true == emb_avl->LL_rot( emb_avl->biroot()) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT( 2 == temp1->data && 1 == temp1->pRight->data && 3 == temp1->pLeft->data );
    //checking: pointers
    CPPUNIT_ASSERT( NULL == temp1->pup && temp1 == temp1->pRight->pup && temp1 == temp1->pLeft->pup );
    //checking: balance
    CPPUNIT_ASSERT( 0 == temp1->bt && 0 == temp1->pRight->bt && 0 == temp1->pLeft->bt );

    emb_avl->rem_left(NULL);
    //create test tree:
    /*
     *    0     4   8
     *    4     9   10
     *    8  -   -
     *    9  20  -
     *   10     -   21
     *   20  -   -
     *   21  -   -
     */
    temp1 = emb_avl->ins_right( NULL, 0 );   temp1->bt = 2;
    emb_avl->ins_right( temp1, 8 );             temp1->pRight->bt = 0;
    temp1 = emb_avl->ins_left( temp1, 4 );   temp1->bt = 0;
    temp1 = emb_avl->ins_left( temp1, 9 );     temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 20 );  temp1->bt = 0;
    temp1 = emb_avl->biroot()->pLeft;
    temp1 = emb_avl->ins_right( temp1, 10 ); temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 21 ); temp1->bt = 0;
    CPPUNIT_ASSERT( true == emb_avl->LL_rot( emb_avl->biroot()) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT( 4 == temp1->data && 0 == temp1->pRight->data && 9 == temp1->pLeft->data &&
                    20 == temp1->pLeft->pLeft->data && 10 == temp1->pRight->pLeft->data && 8 == temp1->pRight->pRight->data &&
                    21 ==  temp1->pRight->pLeft->pRight->data &&
                    NULL == temp1->pLeft->pRight && NULL == temp1->pLeft->pLeft->pLeft && NULL == temp1->pLeft->pLeft->pRight &&
                    NULL == temp1->pRight->pLeft->pLeft &&  NULL == temp1->pRight->pLeft->pRight->pLeft &&  NULL == temp1->pRight->pLeft->pRight->pRight &&
                    NULL == temp1->pRight->pRight->pLeft && NULL == temp1->pRight->pRight->pRight);
    //checking: pointers
    CPPUNIT_ASSERT( NULL == temp1->pup && 4 == temp1->pRight->pup->data && 4 == temp1->pLeft->pup->data &&
                    9 == temp1->pLeft->pLeft->pup->data && 0 == temp1->pRight->pLeft->pup->data &&
                    10 == temp1->pRight->pLeft->pRight->pup->data && 0 == temp1->pRight->pRight->pup->data );
    //checking: balance
    CPPUNIT_ASSERT( -1 == temp1->bt &&
                    1 == temp1->pRight->bt &&
                    1 == temp1->pLeft->bt &&
                    0 == temp1->pLeft->pLeft->bt &&
                    -1 == temp1->pRight->pLeft->bt &&
                    0 == temp1->pRight->pRight->bt &&
                    0 == temp1->pRight->pLeft->pRight->bt
                    );
}

//***************************************************************************
// Testing method: RL_rot()
//***************************************************************************
void AvlTree_TestSuite::test_RL_rot_emb(void){

    BTNode<int>* temp1;
    //create a simple test tree:
    /*
     *   1    - 2
     *   2    3 -
     *   3    - -
     */
    temp1 = emb_avl->ins_right( NULL, 1 );  temp1->bt = -2;
    temp1 = emb_avl->ins_right( temp1, 2 ); temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 3 ); temp1->bt = 0;

    temp1 = emb_avl->biroot();

    //negative - bt out of scope
    temp1->bt = -2;
    temp1->pRight->bt = -1;
    CPPUNIT_ASSERT( false == emb_avl->RL_rot( emb_avl->biroot()) );

    //negative - bt out of scope
    temp1->bt = 2;
    temp1->pRight->bt = -1;
    CPPUNIT_ASSERT( false == emb_avl->RL_rot( emb_avl->biroot()) );

    //negative - bt out of scope
    temp1->bt = 2;
    temp1->pRight->bt = 1;
    CPPUNIT_ASSERT( false == emb_avl->RL_rot( emb_avl->biroot()) );

    //positive - bt OK
    temp1->bt = -2;
    temp1->pRight->bt = 1;
    CPPUNIT_ASSERT( true == emb_avl->RL_rot( emb_avl->biroot()) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT( 3 == temp1->data && 2 == temp1->pRight->data && 1 == temp1->pLeft->data );
    //checking: pointers
    CPPUNIT_ASSERT( NULL == temp1->pup && temp1 == temp1->pRight->pup && temp1 == temp1->pLeft->pup );
    //checking: balance
    CPPUNIT_ASSERT( 0 == temp1->bt && 0 == temp1->pRight->bt && 0 == temp1->pLeft->bt );

    emb_avl->rem_left(NULL);

    //create test tree:
    /*
     * 0    1    2
     * 1    3   4
     * 2    50  5
     * 3    6   -
     * 4    7      8
     * 5    52     9
     * 6    -      -
     * 7    10  11
     * 8    -      12
     * 9    -      13
     * 10   -      -
      * 11   -     14
     * 12   -     -
     * 13   -     -
     * 14   -     -
     * 50    51  -
     * 51   -   -
     * 52   -   -
     *
     */
    temp1 = emb_avl->ins_right( NULL, 0 );            temp1->bt = 1;
            emb_avl->ins_left( temp1, 1 );            temp1->pLeft->bt = -2;
    temp1 = emb_avl->ins_right( temp1, 2 );            temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 5 );            temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 9 );            temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 13 );        temp1->bt = 0;
    temp1 = emb_avl->biroot()->pLeft;                /*1*/
    temp1 = emb_avl->ins_left( temp1, 3 );            temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 6 );            temp1->bt = 0;
    temp1 = emb_avl->biroot()->pLeft;                /*1*/
    temp1 = emb_avl->ins_right( temp1, 4 );            temp1->bt = 1;
    temp1 = emb_avl->ins_right( temp1, 8 );            temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 12 );        temp1->bt = 0;
    temp1 = emb_avl->biroot()->pLeft->pRight;        /*4*/
    temp1 = emb_avl->ins_left( temp1, 7 );            temp1->bt = -1;
    temp1 = emb_avl->ins_left( temp1, 10 );            temp1->bt = 0;
    temp1 = emb_avl->biroot()->pLeft->pRight->pLeft;/*7*/
    temp1 = emb_avl->ins_right( temp1, 11 );        temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 14 );        temp1->bt = 0;
    temp1 = emb_avl->biroot()->pRight;                 /*2*/
    temp1 = emb_avl->ins_left( temp1, 50 );            temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 51 );            temp1->bt =  0;
    temp1 = emb_avl->biroot()->pRight->pRight;      /*5*/
    temp1 = emb_avl->ins_left( temp1, 52 );            temp1->bt =  0;

    CPPUNIT_ASSERT( true == emb_avl->RL_rot( emb_avl->biroot()->pLeft) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT(  0  == temp1->data &&
                     7  == temp1->pLeft->data &&
                     2  == temp1->pRight->data &&
                     1  == temp1->pLeft->pLeft->data &&
                     4  == temp1->pLeft->pRight->data &&
                     50 == temp1->pRight->pLeft->data &&
                     5  == temp1->pRight->pRight->data &&
                     3  == temp1->pLeft->pLeft->pLeft->data &&
                     10 == temp1->pLeft->pLeft->pRight->data &&
                     11 == temp1->pLeft->pRight->pLeft->data &&
                     8  == temp1->pLeft->pRight->pRight->data &&
                     51 == temp1->pRight->pLeft->pLeft->data &&
                     52 == temp1->pRight->pRight->pLeft->data &&
                     9  == temp1->pRight->pRight->pRight->data &&
                     6  == temp1->pLeft->pLeft->pLeft->pLeft->data &&
                     14 == temp1->pLeft->pRight->pLeft->pRight->data &&
                     12 == temp1->pLeft->pRight->pRight->pRight->data &&
                     13 == temp1->pRight->pRight->pRight->pRight->data
                   );
    //checking: pointers
    CPPUNIT_ASSERT(  NULL  == temp1->pup &&
                    temp1  == temp1->pLeft->pup &&
                    temp1  == temp1->pRight->pup &&
                    temp1->pLeft  == temp1->pLeft->pLeft->pup &&
                    temp1->pLeft  == temp1->pLeft->pRight->pup &&
                    temp1->pRight == temp1->pRight->pLeft->pup &&
                    temp1->pRight  == temp1->pRight->pRight->pup &&
                    temp1->pLeft->pLeft  == temp1->pLeft->pLeft->pLeft->pup &&
                    temp1->pLeft->pLeft == temp1->pLeft->pLeft->pRight->pup &&
                    temp1->pLeft->pRight == temp1->pLeft->pRight->pLeft->pup &&
                    temp1->pLeft->pRight  == temp1->pLeft->pRight->pRight->pup &&
                    temp1->pRight->pLeft == temp1->pRight->pLeft->pLeft->pup &&
                    temp1->pRight->pRight == temp1->pRight->pRight->pLeft->pup &&
                    temp1->pRight->pRight  == temp1->pRight->pRight->pRight->pup &&
                    temp1->pLeft->pLeft->pLeft  == temp1->pLeft->pLeft->pLeft->pLeft->pup &&
                    temp1->pLeft->pRight->pLeft == temp1->pLeft->pRight->pLeft->pRight->pup &&
                    temp1->pLeft->pRight->pRight == temp1->pLeft->pRight->pRight->pRight->pup &&
                    temp1->pRight->pRight->pRight == temp1->pRight->pRight->pRight->pRight->pup
                  );
    //checking: balance
    CPPUNIT_ASSERT(  1  == temp1->bt &&
                     0  == temp1->pLeft->bt &&
                     -1  == temp1->pRight->bt &&
                     1  == temp1->pLeft->pLeft->bt &&
                     0  == temp1->pLeft->pRight->bt &&
                     1 == temp1->pRight->pLeft->bt &&
                     -1  == temp1->pRight->pRight->bt &&
                     1  == temp1->pLeft->pLeft->pLeft->bt &&
                     0 == temp1->pLeft->pLeft->pRight->bt &&
                     -1 == temp1->pLeft->pRight->pLeft->bt &&
                     -1  == temp1->pLeft->pRight->pRight->bt &&
                     0 == temp1->pRight->pLeft->pLeft->bt &&
                     0 == temp1->pRight->pRight->pLeft->bt &&
                     -1  == temp1->pRight->pRight->pRight->bt &&
                     0  == temp1->pLeft->pLeft->pLeft->pLeft->bt &&
                     0 == temp1->pLeft->pRight->pLeft->pRight->bt &&
                     0 == temp1->pLeft->pRight->pRight->pRight->bt &&
                     0 == temp1->pRight->pRight->pRight->pRight->bt
                     );
}

//***************************************************************************
// Testing method: LR_rot()
//***************************************************************************
void AvlTree_TestSuite::test_LR_rot_emb(void){

    BTNode<int>* temp1;
    //create a simple test tree:
    /*
     *   1    2 -
     *   2    - 3
     *   3    - -
     */
    temp1 = emb_avl->ins_left( NULL, 1 );  temp1->bt = 2;
    temp1 = emb_avl->ins_left( temp1, 2 ); temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 3 ); temp1->bt = 0;

    temp1 = emb_avl->biroot();

    //negative - bt out of scope
    temp1->bt = -2;
    temp1->pLeft->bt = -1;
    CPPUNIT_ASSERT( false == emb_avl->LR_rot( emb_avl->biroot()) );

    //negative - bt out of scope
    temp1->bt = -2;
    temp1->pLeft->bt = 1;
    CPPUNIT_ASSERT( false == emb_avl->LR_rot( emb_avl->biroot()) );

    //negative - bt out of scope
    temp1->bt = 2;
    temp1->pLeft->bt = 1;
    CPPUNIT_ASSERT( false == emb_avl->LR_rot( emb_avl->biroot()) );

    //positive - bt OK
    temp1->bt = 2;
    temp1->pLeft->bt = -1;
    CPPUNIT_ASSERT( true == emb_avl->LR_rot( emb_avl->biroot()) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT( 3 == temp1->data && 1 == temp1->pRight->data && 2 == temp1->pLeft->data );
    //checking: pointers
    CPPUNIT_ASSERT( NULL == temp1->pup && temp1 == temp1->pRight->pup && temp1 == temp1->pLeft->pup );
    //checking: balance
    CPPUNIT_ASSERT( 0 == temp1->bt && 0 == temp1->pRight->bt && 0 == temp1->pLeft->bt );

    emb_avl->rem_left(NULL);
    //create test tree:
    /*
     * 0    1    2
     * 1    3    4
     * 2    5    6
     * 3    7    8
     * 4    -    9
     * 5    10    -
     * 6    11    12
     * 7    13    -
     * 8    14    15
     * 9    -    -
     * 10    -    -
      * 11    -    -
     * 12    -    16
     * 13    -    -
     * 14    17    -
     * 15    -    -
     * 16    -    -
     * 17    -    -
     *
     */
    temp1 = emb_avl->ins_left( NULL, 0 );            temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 1 );            temp1->bt = 2;
    temp1 = emb_avl->ins_left( temp1, 3 );            temp1->bt = -1;
    temp1 = emb_avl->ins_left( temp1, 7 );            temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 13 );            temp1->bt = 0;
    temp1 = emb_avl->pRoot;
    temp1 = emb_avl->ins_right( temp1, 2 );            temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 6 );            temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 12 );        temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 16 );        temp1->bt = 0;
    temp1 = emb_avl->pRoot->pLeft;
    temp1 = emb_avl->ins_right( temp1, 4 );            temp1->bt = -1;
    temp1 = emb_avl->ins_right( temp1, 9 );            temp1->bt = 0;
    temp1 = emb_avl->pRoot->pLeft->pLeft;
    temp1 = emb_avl->ins_right( temp1, 8 );            temp1->bt = 1;
    temp1 = emb_avl->ins_right( temp1, 15 );        temp1->bt = 0;
    temp1 = emb_avl->pRoot->pLeft->pLeft->pRight;
    temp1 = emb_avl->ins_left( temp1, 14 );            temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 17 );            temp1->bt = 0;
    temp1 = emb_avl->pRoot->pRight;
    temp1 = emb_avl->ins_left( temp1, 5 );            temp1->bt = 1;
    temp1 = emb_avl->ins_left( temp1, 10 );            temp1->bt = 0;
    temp1 = emb_avl->pRoot->pRight->pRight;
    temp1 = emb_avl->ins_left( temp1, 11 );            temp1->bt = 0;

    CPPUNIT_ASSERT( true == emb_avl->LR_rot( emb_avl->biroot()->pLeft) );
    temp1 = emb_avl->biroot();
    //checking: data
    CPPUNIT_ASSERT(  0  == temp1->data &&
                     1  == temp1->pLeft->pRight->data &&
                     2  == temp1->pRight->data &&
                     3  == temp1->pLeft->pLeft->data &&
                     4  == temp1->pLeft->pRight->pRight->data &&
                     5  == temp1->pRight->pLeft->data &&
                     6  == temp1->pRight->pRight->data &&
                     7  == temp1->pLeft->pLeft->pLeft->data &&
                     8  == temp1->pLeft->data &&
                     9  == temp1->pLeft->pRight->pRight->pRight->data &&
                     10  == temp1->pRight->pLeft->pLeft->data &&
                     11  == temp1->pRight->pRight->pLeft->data &&
                     12  == temp1->pRight->pRight->pRight->data &&
                     13  == temp1->pLeft->pLeft->pLeft->pLeft->data &&
                     14  == temp1->pLeft->pLeft->pRight->data &&
                     15  == temp1->pLeft->pRight->pLeft->data &&
                     16  == temp1->pRight->pRight->pRight->pRight->data &&
                     17  == temp1->pLeft->pLeft->pRight->pLeft->data
                 );
    //checking: pointers
    CPPUNIT_ASSERT(  NULL  == temp1->pup &&
                     temp1  == temp1->pLeft->pup &&
                     temp1  == temp1->pRight->pup &&
                     temp1->pLeft  == temp1->pLeft->pLeft->pup &&
                     temp1->pLeft  == temp1->pLeft->pRight->pup &&
                     temp1->pRight == temp1->pRight->pLeft->pup &&
                     temp1->pRight  == temp1->pRight->pRight->pup &&
                     temp1->pLeft->pLeft  == temp1->pLeft->pLeft->pLeft->pup &&
                     temp1->pLeft->pLeft == temp1->pLeft->pLeft->pRight->pup &&
                     temp1->pLeft->pRight == temp1->pLeft->pRight->pLeft->pup &&
                     temp1->pLeft->pRight  == temp1->pLeft->pRight->pRight->pup &&
                     temp1->pRight->pLeft == temp1->pRight->pLeft->pLeft->pup &&
                     temp1->pRight->pRight == temp1->pRight->pRight->pLeft->pup &&
                     temp1->pRight->pRight  == temp1->pRight->pRight->pRight->pup &&
                     temp1->pLeft->pLeft->pLeft  == temp1->pLeft->pLeft->pLeft->pLeft->pup &&
                     temp1->pLeft->pRight->pRight == temp1->pLeft->pRight->pRight->pRight->pup &&
                     temp1->pRight->pRight->pRight == temp1->pRight->pRight->pRight->pRight->pup
                  );
    //checking: balance
    CPPUNIT_ASSERT(  1  == temp1->bt &&
                     -1  == temp1->pLeft->pRight->bt &&
                     -1  == temp1->pRight->bt &&
                     0  == temp1->pLeft->pLeft->bt &&
                     -1  == temp1->pLeft->pRight->pRight->bt &&
                     1  == temp1->pRight->pLeft->bt &&
                     -1  == temp1->pRight->pRight->bt &&
                     1  == temp1->pLeft->pLeft->pLeft->bt &&
                     0  == temp1->pLeft->bt &&
                     0  == temp1->pLeft->pRight->pRight->pRight->bt &&
                     0  == temp1->pRight->pLeft->pLeft->bt &&
                     0  == temp1->pRight->pRight->pLeft->bt &&
                     -1  == temp1->pRight->pRight->pRight->bt &&
                     0  == temp1->pLeft->pLeft->pLeft->pLeft->bt &&
                     1  == temp1->pLeft->pLeft->pRight->bt &&
                     0  == temp1->pLeft->pRight->pLeft->bt &&
                     0  == temp1->pRight->pRight->pRight->pRight->bt &&
                     0  == temp1->pLeft->pLeft->pRight->pLeft->bt
                 );
}

//***************************************************************************
// Testing method: rot()
//***************************************************************************
void AvlTree_TestSuite::test_rot_emb(void){

    BTNode<int>* temp;

    //////////////////////////////////
    //checking RR:
    //////////////////////////////////
    //create a simple test tree:
    /*
     *   1    - 2
     *   2    - 3
     *   3    - -
     */
    temp = emb_avl->ins_right( NULL, 1 ); temp->bt = -2;
    temp = emb_avl->ins_right( temp, 2 ); temp->bt = -1;
    temp = emb_avl->ins_right( temp, 3 ); temp->bt =  0;
    CPPUNIT_ASSERT( RR == emb_avl->rot(emb_avl->biroot()) );
    emb_avl->rem_left(NULL);

    //create a simple test tree:
    /*
     *   1    - 2
     *   2  4 3
     *   3    - -
     *   4  - -
     */
    temp = emb_avl->ins_right( NULL, 1 );                         temp->bt = -2;
    temp = emb_avl->ins_right( temp, 2 );                         temp->bt =  0;
    temp = emb_avl->ins_right( temp, 3 );                         temp->bt =  0;
    temp = emb_avl->ins_left ( emb_avl->biroot()->pRight, 4 );  temp->bt =  0;
    CPPUNIT_ASSERT( RR == emb_avl->rot(emb_avl->biroot()) );
    emb_avl->rem_left(NULL);

    //////////////////////////////////
    //checking LL:
    //////////////////////////////////
    //create a simple test tree:
    /*
     *   1    2 -
     *   2    3 -
     *   3    - -
     */
    temp = emb_avl->ins_left( NULL, 1 ); temp->bt =  2;
    temp = emb_avl->ins_left( temp, 2 ); temp->bt =  1;
    temp = emb_avl->ins_left( temp, 3 ); temp->bt =  0;
    CPPUNIT_ASSERT( LL == emb_avl->rot(emb_avl->biroot()) );
    emb_avl->rem_left(NULL);

    //create a simple test tree:
    /*
     *   1  2 -
     *   2  3 4
     *   3  - -
     *   4  - -
     */
    temp = emb_avl->ins_left( NULL, 1 );                       temp->bt =  2;
    temp = emb_avl->ins_left( temp, 2 );                       temp->bt =  0;
    temp = emb_avl->ins_left( temp, 3 );                       temp->bt =  0;
    temp = emb_avl->ins_right( emb_avl->biroot()->pLeft, 4 ); temp->bt =  0;
    CPPUNIT_ASSERT( LL == emb_avl->rot(emb_avl->biroot()) );
    emb_avl->rem_left(NULL);

    //////////////////////////////////
    //checking RL:
    //////////////////////////////////
    //create a simple test tree:
    /*
     *   1    - 2
     *   2    3 -
     *   3    - -
     */
    temp = emb_avl->ins_right( NULL, 1 );      temp->bt = -2;
    temp = emb_avl->ins_right( temp, 2 );     temp->bt = 1;
    temp = emb_avl->ins_left( temp, 3 );    temp->bt = 0;
    CPPUNIT_ASSERT( RL == emb_avl->rot(emb_avl->biroot()) );
    emb_avl->rem_left(NULL);

    //////////////////////////////////
    //checking LR:
    //////////////////////////////////
    //create a simple test tree:
    /*
     *   1    2 -
     *   2    - 3
     *   3    - -
     */
    temp = emb_avl->ins_left( NULL, 1 );    temp->bt = 2;
    temp = emb_avl->ins_left( temp, 2 );     temp->bt = -1;
    temp = emb_avl->ins_right( temp, 3 );     temp->bt = 0;
    CPPUNIT_ASSERT( LR == emb_avl->rot(emb_avl->biroot()) );
    emb_avl->rem_left(NULL);

    //////////////////////////////////
    //checking NONE (tree's balanced):
    //////////////////////////////////
    //create a simple test tree:
    /*
     *   1  2 5
     *   2  3 4
     *   3  - -
     *   4  - -
     *   5  - -
     */
    temp = emb_avl->ins_left( NULL, 1 );                        temp->bt = 1;
    temp = emb_avl->ins_left( temp, 2 );                         temp->bt = 0;
    temp = emb_avl->ins_left( temp, 3 );                         temp->bt = 0;
    temp = emb_avl->ins_right( emb_avl->biroot()->pLeft, 4 );     temp->bt = 0;
    temp = emb_avl->ins_right( emb_avl->biroot(), 5 );             temp->bt = 0;
    CPPUNIT_ASSERT( LL != emb_avl->rot(emb_avl->biroot()) );
    CPPUNIT_ASSERT( RR != emb_avl->rot(emb_avl->biroot()) );
    CPPUNIT_ASSERT( RL != emb_avl->rot(emb_avl->biroot()) );
    CPPUNIT_ASSERT( LR != emb_avl->rot(emb_avl->biroot()) );
    CPPUNIT_ASSERT( NONE == emb_avl->rot(emb_avl->biroot()) );
    emb_avl->rem_left(NULL);
}

//***************************************************************************
// Testing method: ins()
//***************************************************************************
void AvlTree_TestSuite::test_ins_emb(void){

    BTNode<int>* temp1;
    BTNode<int>* temp2;
    ////////////////////////////////////////////////////
    //Insert data to empty tree
    ////////////////////////////////////////////////////
    // 10 - -
    ////////////////////////////////////////////////////
    temp1 = emb_avl->ins( 10 );
    CPPUNIT_ASSERT( 1 == emb_avl->size() &&
                    10 == emb_avl->pRoot->data &&
                    10 == temp1->data &&
                    NULL == emb_avl->pRoot->pup &&
                    NULL == temp1->pup &&
                    0 == emb_avl->pRoot->bt &&
                    0 == temp1->bt
            );
    ////////////////////////////////////////////////////
    //Continue to build fully balanced tree (no rotation
    //needed so far)
    ////////////////////////////////////////////////////
    // 10 6 -
    // 6  - -
    ////////////////////////////////////////////////////
    temp1 = emb_avl->ins( 6 );
    CPPUNIT_ASSERT( 2 == emb_avl->size() &&
                    6 == temp1->data &&
                    emb_avl->pRoot == temp1->pup &&
                    0 == temp1->bt &&
                    1 == emb_avl->pRoot->bt
            );
    ////////////////////////////////////////////////////
    //Continue to build fully balanced tree (no rotation
    //needed so far)
    ////////////////////////////////////////////////////
    // 10 6 16
    // 6  - -
    // 16 - -
    ////////////////////////////////////////////////////
    temp1 = emb_avl->ins( 16 );
    CPPUNIT_ASSERT( 3 == emb_avl->size() &&
                    16 == temp1->data &&
                    emb_avl->pRoot == temp1->pup &&
                    0 == temp1->bt &&
                    0 == emb_avl->pRoot->bt
            );
    ////////////////////////////////////////////////////
    //Continue to build fully balanced tree (no rotation
    //needed so far)
    ////////////////////////////////////////////////////
    // 10 6 16
    // 6  5 -
    // 16 - -
    // 5  - -
    ////////////////////////////////////////////////////
    temp1 = emb_avl->ins( 5 );
    CPPUNIT_ASSERT( 4 == emb_avl->size() &&
                    5 == temp1->data &&
                    emb_avl->pRoot->pLeft == temp1->pup &&
                    1 == emb_avl->pRoot->bt &&
                    0 == emb_avl->pRoot->pRight->bt &&
                    1 == emb_avl->pRoot->pLeft->bt &&
                    0 == temp1->bt
            );
    ////////////////////////////////////////////////////
    //Continue to build fully balanced tree (no rotation
    //needed so far)
    ////////////////////////////////////////////////////
    // 10 6 16
    // 6  5 7
    // 16 - -
    // 5  - -
    // 7  - -
    ////////////////////////////////////////////////////
    temp1 = emb_avl->ins( 7 );
    CPPUNIT_ASSERT( 5 == emb_avl->size() &&
                    7 == temp1->data &&
                    emb_avl->pRoot->pLeft == temp1->pup &&
                    1 == emb_avl->pRoot->bt &&
                    0 == emb_avl->pRoot->pRight->bt &&
                    0 == emb_avl->pRoot->pLeft->bt &&
                    0 == emb_avl->pRoot->pLeft->pLeft->bt &&
                    0 == temp1->bt
            );
    ////////////////////////////////////////////////////
    //A new data throw tree off balance.
    //LL conversion will be applied.
    ////////////////////////////////////////////////////
    // 10 6 16        2
    // 6  5 7        1
    // 16 - -        0
    // 5  4 -        1
    // 7  - -        0
    // 4  - -        0
    // ----------------------
    // after LL conversion:
    // 6   5 10        0
    // 5   4 -        1
    // 10  7 16        0
    // 4   - -        0
    // 7   - -        0
    // 16  - -        0
    ////////////////////////////////////////////////////
    temp1 = emb_avl->ins( 4 );
    CPPUNIT_ASSERT( 6 == emb_avl->size() &&
                    4 == temp1->data &&
                    //check if data ok:
                    6 == emb_avl->pRoot->data &&
                    5 == emb_avl->pRoot->pLeft->data &&
                    10 == emb_avl->pRoot->pRight->data &&
                    4 == emb_avl->pRoot->pLeft->pLeft->data &&
                    7 == emb_avl->pRoot->pRight->pLeft->data &&
                    16 == emb_avl->pRoot->pRight->pRight->data &&
                    //check if bt ok:
                    0 == emb_avl->pRoot->bt &&
                    1 == emb_avl->pRoot->pLeft->bt &&
                    0 == emb_avl->pRoot->pRight->bt &&
                    0 == emb_avl->pRoot->pLeft->pLeft->bt &&
                    0 == emb_avl->pRoot->pRight->pLeft->bt &&
                    0 == emb_avl->pRoot->pRight->pRight->bt

            );
    emb_avl->rem_left(NULL);
    //////////////////////////////////////////////////////////////////
    //Insert random data is specified order.
    //////////////////////////////////////////////////////////////////
    // input: 26 19 34 16 2 21 9 13 21 3 31 14 1 10 40 12 22 22 14 36
    // output:
    // 19    9    26
    // 9    2    14
    // 26    21    34
    // 2    1    3
    // 14    12    16
    // 21    21    22
    // 34    31    40
    // 1    -    -
    // 3    -    -
    // 12    10    13
    // 16    14    -
    // 21    -    -
    // 22    -    22
    // 31    -    -
    // 40    36    -
    // 10    -    -
    // 13    -    -
    // 14    -    -
    // 22    -    -
    // 36    -    -
    //////////////////////////////////////////////////////////////////
    int buff[] = { 26, 19, 34, 16, 2, 21, 9, 13, 21, 3, 31, 14, 1, 10, 40, 12, 22, 22, 14, 36 };
    for( int i = 0; i<20; i++ )
    {
        temp1 = emb_avl->ins( buff[i] );

        //middle checking:
        if( i==4 ){
            CPPUNIT_ASSERT( 5 == emb_avl->size() &&
                            //check if data ok:
                            26 == emb_avl->pRoot->data &&
                            16 == emb_avl->pRoot->pLeft->data &&
                            34 == emb_avl->pRoot->pRight->data &&
                            2  == emb_avl->pRoot->pLeft->pLeft->data &&
                            19 == emb_avl->pRoot->pLeft->pRight->data &&
                            //check if bt ok:
                            1 == emb_avl->pRoot->bt &&
                            0 == emb_avl->pRoot->pLeft->bt &&
                            0 == emb_avl->pRoot->pRight->bt &&
                            0 == emb_avl->pRoot->pLeft->pLeft->bt &&
                            0 == emb_avl->pRoot->pLeft->pRight->bt
            );
        }else if( i == 5 ){
            CPPUNIT_ASSERT( 6 == emb_avl->size() &&
                            //check if data ok:
                            19 == emb_avl->pRoot->data &&
                            16 == emb_avl->pRoot->pLeft->data &&
                            26 == emb_avl->pRoot->pRight->data &&
                            2  == emb_avl->pRoot->pLeft->pLeft->data &&
                            21 == emb_avl->pRoot->pRight->pLeft->data &&
                            34 == emb_avl->pRoot->pRight->pRight->data &&
                            //check if bt ok:
                            0 == emb_avl->pRoot->bt &&
                            1 == emb_avl->pRoot->pLeft->bt &&
                            0 == emb_avl->pRoot->pRight->bt &&
                            0 == emb_avl->pRoot->pLeft->pLeft->bt &&
                            0 == emb_avl->pRoot->pRight->pLeft->bt &&
                            0 == emb_avl->pRoot->pRight->pRight->bt
            );
        }else if( i == 8 ){
            CPPUNIT_ASSERT( 9 == emb_avl->size() &&
                            //check if data ok:
                            19 == emb_avl->pRoot->data &&
                            9  == emb_avl->pRoot->pLeft->data &&
                            26 == emb_avl->pRoot->pRight->data &&
                            2  == emb_avl->pRoot->pLeft->pLeft->data &&
                            16 == emb_avl->pRoot->pLeft->pRight->data &&
                            21 == emb_avl->pRoot->pRight->pLeft->data &&
                            34 == emb_avl->pRoot->pRight->pRight->data &&
                            13 == emb_avl->pRoot->pLeft->pRight->pLeft->data &&
                            21 == emb_avl->pRoot->pRight->pLeft->pRight->data &&
                            //check if bt ok:
                            0  == emb_avl->pRoot->bt &&
                            -1 == emb_avl->pRoot->pLeft->bt &&
                            1  == emb_avl->pRoot->pRight->bt &&
                            0  == emb_avl->pRoot->pLeft->pLeft->bt &&
                            1  == emb_avl->pRoot->pLeft->pRight->bt &&
                            -1 == emb_avl->pRoot->pRight->pLeft->bt &&
                            0  == emb_avl->pRoot->pRight->pRight->bt &&
                            0  == emb_avl->pRoot->pLeft->pRight->pLeft->bt &&
                            0  == emb_avl->pRoot->pRight->pLeft->pRight->bt
            );
        }else if( i == 19 ){
            CPPUNIT_ASSERT( 20 == emb_avl->size() &&
                            //check if data ok:
                            19 == emb_avl->pRoot->data &&
                            9  == emb_avl->pRoot->pLeft->data &&
                            26 == emb_avl->pRoot->pRight->data &&
                            2  == emb_avl->pRoot->pLeft->pLeft->data &&
                            14 == emb_avl->pRoot->pLeft->pRight->data &&
                            21 == emb_avl->pRoot->pRight->pLeft->data &&
                            34 == emb_avl->pRoot->pRight->pRight->data &&
                            1  == emb_avl->pRoot->pLeft->pLeft->pLeft->data &&
                            3  == emb_avl->pRoot->pLeft->pLeft->pRight->data &&
                            12 == emb_avl->pRoot->pLeft->pRight->pLeft->data &&
                            16 == emb_avl->pRoot->pLeft->pRight->pRight->data &&
                            21 == emb_avl->pRoot->pRight->pLeft->pLeft->data &&
                            22 == emb_avl->pRoot->pRight->pLeft->pRight->data &&
                            31 == emb_avl->pRoot->pRight->pRight->pLeft->data &&
                            40 == emb_avl->pRoot->pRight->pRight->pRight->data &&
                            10 == emb_avl->pRoot->pLeft->pRight->pLeft->pLeft->data &&
                            13 == emb_avl->pRoot->pLeft->pRight->pLeft->pRight->data &&
                            14 == emb_avl->pRoot->pLeft->pRight->pRight->pLeft->data &&
                            22 == emb_avl->pRoot->pRight->pLeft->pRight->pRight->data &&
                            36 == emb_avl->pRoot->pRight->pRight->pRight->pLeft->data &&
                            //check if bt ok:
                             0 == emb_avl->pRoot->bt &&
                            -1 == emb_avl->pRoot->pLeft->bt &&
                             0 == emb_avl->pRoot->pRight->bt &&
                             0 == emb_avl->pRoot->pLeft->pLeft->bt &&
                             0 == emb_avl->pRoot->pLeft->pRight->bt &&
                            -1 == emb_avl->pRoot->pRight->pLeft->bt &&
                            -1 == emb_avl->pRoot->pRight->pRight->bt &&
                             0 == emb_avl->pRoot->pLeft->pLeft->pLeft->bt &&
                             0 == emb_avl->pRoot->pLeft->pLeft->pRight->bt &&
                             0 == emb_avl->pRoot->pLeft->pRight->pLeft->bt &&
                             1 == emb_avl->pRoot->pLeft->pRight->pRight->bt &&
                             0 == emb_avl->pRoot->pRight->pLeft->pLeft->bt &&
                            -1 == emb_avl->pRoot->pRight->pLeft->pRight->bt &&
                             0 == emb_avl->pRoot->pRight->pRight->pLeft->bt &&
                             1 == emb_avl->pRoot->pRight->pRight->pRight->bt &&
                             0 == emb_avl->pRoot->pLeft->pRight->pLeft->pLeft->bt &&
                             0 == emb_avl->pRoot->pLeft->pRight->pLeft->pRight->bt &&
                             0 == emb_avl->pRoot->pLeft->pRight->pRight->pLeft->bt &&
                             0 == emb_avl->pRoot->pRight->pLeft->pRight->pRight->bt &&
                             0 == emb_avl->pRoot->pRight->pRight->pRight->pLeft->bt
            );
        }
    }
    std::cout<<*emb_avl<<std::endl;
}
